"""我们考虑 L×L(L=150)的方格矩阵（方格矩阵满足周期性边界条件），
其中每个格点有概论p被占据。当一个被占据的格点d_0的相邻格点d_n（上下左右）同样被占据时，我们认为d_0 和d_n同属一个团簇。

1，假设共有s个团簇，第x个团簇的大小为C_x则，计算最大团簇和次大团簇（第二大团）各自，随着概论p从0到1的变化。
2，计算团簇的平均大小随着，概率p从0到1的变化。
3，计算在不同的概率p中团簇尺寸的分布情况。当（p<pc）时，统计所有团簇；当（p>pc）时，统计除最大团簇之外的所有团簇。
4*，模拟团簇随着概率p从0到1逐渐增加，最大团，次大团（第二大团），的生长过程，并用动画展示出来。
"""

import numpy as np
import matplotlib.pyplot as plt

#定义一个类，找出所有团簇坐标
class Solution:
    def __init__(self, grid):
        self.grid = grid
        n, n = grid.shape #n*n矩阵
        # n*n的全0标签矩阵,0表示该格子没有被遍历过，若已经被遍历，label[i][j]=1
        self.lable = [[0] * n for i in range(n)]

    #判断该格子是否需要被遍历：
    #找出横纵坐标均在范围内，并且数值为1，label = 0的格子
    def Lable(self, i, j, lable, grid):
        n, n = grid.shape
        return i >= 0 and i < n and j >= 0 and j < n and lable[i][j] == 0 and grid[i][j] == 1

    #被遍历过的格子label变成1
    def add(self, i, j, lable, grid, q):
        if self.Lable(i, j, lable, grid):
            q.append([i, j])
            self.lable[i][j] = 1

    #广度优先遍历
    def bfs(self):
        n, n = self.grid.shape
        res = []
        for i in range(n):
            for j in range(n):
                if self.lable[i][j] == 1 or self.grid[i][j] == 0:
                    continue
                P = []
                Q = []
                P.append([i, j])
                self.lable[i][j] = 1
                while P:
                    temp = P.pop(0)
                    Q.append(temp)
                    self.add(temp[0] - 1, temp[1], self.lable, self.grid, P)
                    self.add(temp[0] + 1, temp[1], self.lable, self.grid, P)
                    self.add(temp[0], temp[1] - 1, self.lable, self.grid, P)
                    self.add(temp[0], temp[1] + 1, self.lable, self.grid, P)
                res.append(Q)
        return res  #团簇坐标

def collection(list):  # 统计不同大小的团簇对应的个数
    list_cnt = {}  # 将结果用一个字典存储
    # 统计结果
    for value in list:
        # get(value, num)函数的作用是获取字典中value对应的键值, num=0指示初始值大小。
        list_cnt[value] = list_cnt.get(value, 0) + 1
    return list_cnt

def collection2(list,a):  # 统计最大团簇之外的所有团簇对应的个数
    list_cnt = {}  # 将结果用一个字典存储
    # 统计结果
    for value in list:
        # get(value, num)函数的作用是获取字典中value对应的键值, num=0指示初始值大小。
        list_cnt[value] = list_cnt.get(value, 0) + 1
    del list_cnt[a]
    return list_cnt


if __name__ == '__main__':
    x = []  # 存概率p
    maxarea = []  # 存最大团簇大小
    second_max = []  # 存次大团簇大小
    mean = []  # 存平均团簇大小
    for p in np.arange(0.01, 1.01, 0.01):
        data = np.random.rand(150, 150)
        for i in range(len(data)):
            for j in range(len(data[i])):
                if data[i][j] <= p:
                    data[i][j] = 1
                else:
                    data[i][j] = 0  # 根据不同概率生成0-1矩阵，模拟以不同概率撒点
        s = Solution(data)
        res = s.bfs() # 团簇坐标
        #print(res)
        b = list()
        c = list()
        for i in range(len(res)):
            b.append(len(res[i]))
            c.append(len(res[i]))
        print("当p为{}，生成的团簇大小分别是:{}".format(p, b))
        largest = max(b)
        average = np.mean(b)
        print("最大团簇大小为:", largest)
        print("团簇的平均大小为:", average)
        c.remove(largest)

        if c==[]:
            print("只生成一个团簇，没有次大团簇！")
        else:
            second_large = max(c)
            #b = [b[i] for i in range(len(b)) if b[i] != largest]
            print("次大团簇大小为:", second_large)
        if p <0.59:
            print("不同大小的团簇对应的个数为:", collection(b))
        if p > 0.59:
            print("最大团簇之外的所有团簇对应的个数为:", collection2(b, largest))


        x.append(p)
        maxarea.append(largest)
        second_max.append(second_large)
        mean.append(average)

##############
    # 画图：最大团簇随p变化
    plt.plot(x, maxarea, '.-', label='max' )
    plt.xlabel('p')  # 设置横坐标轴标题
    plt.ylabel('the size of the largest cluster')
    plt.legend()  # 显示图例，即每条线对应 label 中的内容
    plt.title("max-p")
    plt.show()

    # 画图：次大团簇随p变化
    plt.plot(x, second_max, '.-', label='second_max')
    plt.xlabel('p')  # 设置横坐标轴标题
    plt.ylabel('the size of the second_largest cluster')
    plt.legend()  # 显示图例，即每条线对应 label 中的内容
    plt.title("second_max-p")
    plt.show()

    #画图：团簇的平均大小随p变化
    plt.plot(x, mean, '.-', label='mean')
    plt.xlabel('p')  # 设置横坐标轴标题
    plt.ylabel('the average of clusters')
    plt.legend()  # 显示图例，即每条线对应 label 中的内容
    plt.title("average-p")
    plt.show()
#############
